#_*_coding:utf-8_*_
'''
题目：
    剑指offer 17 打印从1 到最大的n位数

    输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。
    比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。


示例 1:
    输入: n = 1
    输出: [1,2,3,4,5,6,7,8,9]
 

说明：
    用返回一个整数列表来代替打印
    n 为正整数


'''
import collections
from typing import List

class Solution:
    def printNumbers1(self, n: int) -> List[int]:
        '''
            注意题目需要从1开始打印
                所以最大的n位数和位数n的关系为：
                    最大的1位数为9
                    最大的2位数为99
                    。。。
                总结一下其公式为： end = 10^n -1

            注意大数越界问题：当n较大时，end会超出 int32 整型的取值范围，超出取值范围
            的数字无法正常存储，但由于本题要求返回 int类型数组，相当于默认所有数字都在
            int32 整型取值范围内，因此不需要考虑大数越界问题。

            复杂度分析：
                时间复杂度： O(10**n)  生成长度为 10**n 的列表需要使用 O(10^n) 时间
                空间复杂度：O(1) 建立列表需要使用 O(1)大小的额外空间
                列表作为返回结果，不计入额外空间
        '''
        res = []
        for i in range(1, 10**n):
            res.append(i)
        return res

    def printNumbers2(self, n: int) -> List[int]:
        '''
            利用Python语言特性，可以简化代码
            使用range()生成可迭代对象，再使用list()方法转换为列表并返回即可
        '''
        return list(range(1, 10**n))


    def printNumbers3(self, n: int) -> List[int]:
        '''
            实际上，本题考查的是大数越界情况下的打印需要解决下面问题：
            1，表示大数的变量类型
                无论是 short int long 任意变量类型，数字的取值范围都是有限的
                因此大数的表示应 用字符串 String类型

            2， 生成数字的字符串集
                使用 int 类型时，每轮可通过 +1 生成下一个数字，而此方法无法应用到
                string类型，并且，string类型的数字的进位操作效率较低
                例如：9999到10000 需要从个位到千位循环判断，进位4次

                观察可知，生成的列表实际上是 n位0~9的全排列，因此可避开进位操作，通过
                递归生成数字的 String 列表

            3，基于分治算法的思想，先固定高位，向低位递归，当个位已被固定时，添加数字
                的字符串。例如当 n=2时（数字范围1~99），固定十位为0~9，按顺序依次开启
                递归，固定个位0~9，终止递归并添加数字字符串。

            若从 0 开始计数，全排列方案共有 10**n 种
            若从 1 开始计数，则方案共有 10**n -1 种

        '''
        def dfs(x):
            if x == n:  # 终止条件：已固定完所有位
                res.append("".join(num))  # 拼接 num 并添加至 res 尾部
                print('cur res:  ', res)
                return None
            for i in range(10):  # 遍历 0~9
                num[x] = str(i)  # 固定第 x 位为 i
                print(num)
                dfs(x+1)         # 开启固定第 x+1 位

        # 起始数字定义为 n个 0组成的字符列表
        num = ['0']*n
        # 数字字符串列表
        res = []
        # 开启全排列递归
        dfs(0)
        # 拼接所有数字字符串，使用逗号隔开，并返回
        return ','.join(res)


    def printNumbers4(self, n: int) -> List[int]:
        '''
            观察3可知，当前生成方法有以下问题：
                1，诸如 00，01,02  应当显示为0,1,2，即应删除高位多余的0
                2，此方法从0 开始生成，而题目要求列表从1开始

            以上1问题的解决方法如下：
                1，删除高位多余的0
                    字符串左边界定义：声明变量 start 规定字符串的左边界，以保证添加的
                    数字字符串 num[start:] 中无高位多余的0。例如当 n=2时，1~9时start=1
                    10~99 start=0

                2，左边界 start 的规律
                    观察可知，当输出数字的所有位都是9时，则下一个数字需要向更高位进1，
                    此时左边界 start 需要减1（即高位多余的0减少一个），例如当 n=3
                    （数字范围1~999），左边界 start 需要减去1的情况有：009 进位到 010
                    099 进位至 100。设数字各位中99 的数量为 nine，所有位都为9的判断条件可
                    用以下公式表示。
                        n - start = nine
                3，统计 nine 的方法
                    固定第 x 位时，当 i=9 则执行 nine=nine+1，并在回溯前恢复 nine =nine-1

            以上2问题的解决方法如下：
                1，在以上方法的基础上，添加数字字符串前判断其是否为 0，若为0，则直接跳过


            复杂度分析：
                时间复杂度O(10**n)  递归的生成的排列的数量为 10**n
                空间复杂度O(10**n)  结果列表res的长度 10**n-1，各数字字符串的长度
                    区间为1,2,...n，因此占用O(10**n) 大小的额外空间
        '''
        def dfs(x):
            if x == n:  # 终止条件：已固定完所有位
                s = ''.join(num[self.start:])
                if s != '0':
                    res.append(s)
                if n - self.start == self.nine:
                    self.start -= 1
                return None

            for i in range(10):  # 遍历 0~9
                if i == 9:
                    self.nine += 1
                num[x] = str(i)  # 固定第 x 位为 i
                print(num)
                dfs(x+1)         # 开启固定第 x+1 位
            self.nine -= 1

        # 起始数字定义为 n个 0组成的字符列表
        num = ['0']*n
        # 数字字符串列表
        res = []
        self.nine = 0
        self.start = n-1

        # 开启全排列递归
        dfs(0)
        # 拼接所有数字字符串，使用逗号隔开，并返回
        return ','.join(res)


print(Solution().printNumbers4(n=1))
'''
    在3的写法找那个，各数字字符串被逗号隔开，共同组成长字符串，返回的数字集字符串
如下所示：
    ['0']
    cur res:   ['0']
    ['1']
    cur res:   ['0', '1']
    ['2']
    cur res:   ['0', '1', '2']
    ['3']
    cur res:   ['0', '1', '2', '3']
    ['4']
    cur res:   ['0', '1', '2', '3', '4']
    ['5']
    cur res:   ['0', '1', '2', '3', '4', '5']
    ['6']
    cur res:   ['0', '1', '2', '3', '4', '5', '6']
    ['7']
    cur res:   ['0', '1', '2', '3', '4', '5', '6', '7']
    ['8']
    cur res:   ['0', '1', '2', '3', '4', '5', '6', '7', '8']
    ['9']
    cur res:   ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
    0,1,2,3,4,5,6,7,8,9

当 n=2时， 输出就为 00, 01, 02, ....98,99

'''
